// hdu3669
// 题意：给定n(<=50000)个矩形的人长hi, 宽wi，有一个无限长宽的墙挡着，
//       现在要挖最多k(<=100)个不重复的矩形的洞，每个洞费用为该洞的
//       长乘以宽。问，最小多少费用让全部人通过。
//
// 题解：一开始想错方向，排序方向错了，把w从小到大排序。结果往单调队列+堆优化方向想了，
//       写了一发发现怎么都不对，往哪个方向想要处理一个区间max{hi}，
//       似乎不太好搞。
//       后来发现把w从大到小排序，转移就好写了。
//
//       先把w按大到小排序，然后对于h，如果比前面的小就直接可以塞到之前的
//       洞里，所以跳过，这样h就是递增的了。考虑dp[i][k]表示前i个人都通过，
//       用了k个洞最小费用，转移就是
//       dp[i][k] = min{ dp[j][k] + w[j + 1]*h[i] } (j<i)
//       这个dp是O(n^2*k)的，需要优化，虽然是二维的，上经典的斜率优化
//       可推得对于 t<j<i，o令Y(i, k) = dp[i][k-1], Xi = -w[i + 1]:
//        (Y(j, k - 1) - Y(t, k - 1)) / (Xj - Xt) <= h[i]
//        h[i]是单增的，所以有效状态是下凸的，用单调队列维护就好。
//
// 统计：858ms, too long, 1wa
//
// run: $exec < bfdiff.in
// opt: 0
// flag: -g
#include <cstdio>
#include <algorithm>

struct data { long long w, h; };

bool operator<(data const & a, data const & b)
{
	return a.w > b.w || (a.w == b.w && a.h < b.h);
}

long long const inf = (long long)(1) << 60;
int const maxn = 50100;
int const maxk = 110;
data da[maxn];
long long dp[maxn][maxk];
int q[4 * maxn][maxk];
int head[maxk], tail[maxk];
int n, k;

long long coord_x(int i) { return -da[i + 1].w; }
long long coord_y(int i, int k) { return dp[i][k - 1]; }
long long slope_x(int i, int j) { return coord_x(i) - coord_x(j); }
long long slope_y(int i, int j, int k) { return coord_y(i, k) - coord_y(j, k); }
bool slope_less(int i1, int j1, int i2, int j2, int k)
{
	return slope_y(i1, j1, k) * slope_x(i2, j2) < slope_y(i2, j2, k) * slope_x(i1, j1);
}

void init()
{
	for (int i = 0; i <= k; i++) head[i] = tail[i] = 1, q[1][i] = 0;
}

int main()
{
	while (std::scanf("%d %d", &n, &k) != EOF) {
		for (int i = 1; i <= n; i++) std::scanf("%lld %lld", &da[i].w, &da[i].h);
		std::sort(da + 1, da + n + 1);

		init();
		int max_height = 0;
		for (int tk = 1; tk <= k; tk++) {
			max_height = 0;
			for (int i = 1; i <= n; i++) {
				if (da[i].h <= max_height) continue;
				max_height = da[i].h;
				while (head[tk] < tail[tk] && slope_y(q[head[tk] + 1][tk], q[head[tk]][tk], tk) <= da[i].h * slope_x(q[head[tk] + 1][tk], q[head[tk]][tk]))
					head[tk]++;

				int j = q[head[tk]][tk];
				dp[i][tk] = dp[j][tk - 1] + da[j + 1].w * da[i].h;

				if (tk == k) continue;
				while (head[tk + 1] < tail[tk + 1] && slope_less(i, q[tail[tk + 1]][tk + 1], q[tail[tk + 1]][tk + 1], q[tail[tk + 1] - 1][tk + 1], tk + 1))
					tail[tk + 1]--;
				q[++tail[tk + 1]][tk + 1] = i;
			}
		}

		int i = 1;
		for (; i <= n; i++) if (da[i].h == max_height) break;
		long long ans = inf;
		for (int j = 1; j <= k; j++)
			ans = std::min(ans, dp[i][j]);
		std::printf("%lld\n", ans);
	}
}

